package com.south.base.test.arithmetic.arrays;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

import static com.south.base.utils.SortUtil.swap;

/**
 * @author Administrator
 * @date 2020/6/24 14:14
 */
public class Sort {
    /**
     * 给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
     */
    @Test
    public void wiggleSort() {
        int[] nums = new int[]{1, 5, 1, 1, 6, 4};
        wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
        nums = new int[]{1, 3, 2, 2, 3, 1};
        wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
        nums = new int[]{1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 2, 2};
        wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 将数据分为大小两部分
     * 再进行穿插组成大数组
     *
     * @param nums
     */
    public void wiggleSort(int[] nums) {
        //排序
        Arrays.sort(nums);
        int len = nums.length, i = 0;
        int[] smaller = new int[len % 2 == 0 ? len / 2 : (len / 2 + 1)], bigger = new int[len / 2];
        //复制
        System.arraycopy(nums, 0, smaller, 0, smaller.length);
        System.arraycopy(nums, smaller.length, bigger, 0, len / 2);
        //穿插
        for (; i < len / 2; i++) {
            nums[2 * i] = smaller[smaller.length - 1 - i];
            nums[2 * i + 1] = bigger[len / 2 - 1 - i];
        }
        if (len % 2 != 0) nums[2 * i] = smaller[smaller.length - 1 - i];
    }

    /**
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     */
    @Test
    public void sortColors() {
        int[] nums = new int[]{2, 0, 2, 1, 1, 0};
        sortColors(nums);
        Assert.assertArrayEquals(new int[]{0, 0, 1, 1, 2, 2}, nums);
    }

    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int red = 0, white = 0;
        for (int num : nums) {
            switch (num) {
                case 0:
                    ++red;
                    break;
                case 1:
                    white++;
                    break;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i < red ? 0 : i < red + white ? 1 : 2;
        }
    }

    /**
     * 下一个排列
     * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
     * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
     * 必须原地修改，只允许使用额外常数空间。
     */
    @Test
    public void nextPermutation() {
        int[] t = new int[]{1, 2, 3};
        nextPermutation(t);
        Assert.assertArrayEquals(new int[]{1, 3, 2}, t);
        t = new int[]{3, 2, 1};
        nextPermutation(t);
        Assert.assertArrayEquals(new int[]{1, 2, 3}, t);
        t = new int[]{1, 1, 5};
        nextPermutation(t);
        Assert.assertArrayEquals(new int[]{1, 5, 1}, t);
    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    /**
     * 前 K 个高频元素
     */
    @Test
    public void topKFrequent() {
        Assert.assertArrayEquals(new int[]{1, 2}, topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2));
        Assert.assertArrayEquals(new int[]{1}, topKFrequent(new int[]{1}, 1));
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        // 取出最小堆中的元素
        int[] res = new int[k];
        int index = k - 1;
        while (!pq.isEmpty() && index >= 0) {
            res[index] = pq.remove();
            index--;
        }
        return res;
    }

    /**
     * 合并区间
     * 给出一个区间的集合，请合并所有重叠的区间。
     */
    @Test
    public void merge() {
        Assert.assertArrayEquals(new int[][]{{1, 6}, {8, 10}, {15, 18}}, merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}}));
        Assert.assertArrayEquals(new int[][]{{1, 6}}, merge(new int[][]{{1, 4}, {4, 6}}));
        Assert.assertArrayEquals(new int[][]{{0, 5}}, merge(new int[][]{{1, 5}, {0, 4}}));
        Assert.assertArrayEquals(new int[][]{{0, 0}, {1, 4}}, merge(new int[][]{{0, 0}, {1, 4}}));
        Assert.assertArrayEquals(new int[][]{{1, 6}, {8, 10}, {15, 18}}, merge2(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}}));
        Assert.assertArrayEquals(new int[][]{{1, 6}}, merge2(new int[][]{{1, 4}, {4, 6}}));
        Assert.assertArrayEquals(new int[][]{{0, 5}}, merge2(new int[][]{{1, 5}, {0, 4}}));
        Assert.assertArrayEquals(new int[][]{{0, 0}, {1, 4}}, merge2(new int[][]{{0, 0}, {1, 4}}));
    }

    public int[][] merge2(int[][] intervals) {
        int len = intervals.length;
        if (len < 2) return intervals;
        List<int[]> list = new ArrayList<>();
        boolean[] f = new boolean[intervals.length];
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (intervals[i][0] <= intervals[j][1] && intervals[i][1] >= intervals[j][0]) {
                    intervals[j][0] = Math.min(intervals[i][0], intervals[j][0]);
                    intervals[j][1] = Math.max(intervals[i][1], intervals[j][1]);
                    intervals[i] = null;
                    f[i] = true;
                    break;
                }
            }
            if (!f[i]) {
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[][]{});
    }

    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, Comparator.comparingInt(v -> v[0]));
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}
